package com.njupt.graphTheory;



import java.util.Deque;
import java.util.LinkedList;
import java.util.Scanner;

/**
 * @Author: wujiaming
 * @CreateTime: 2025/1/31 13:43
 * @Description: 200.岛屿数量
 * @Version: 1.0
 */


public class NumIslands_200 {

    public static final int[][] dir = {{0,1},{1,0},{-1,0},{0,-1}};

    public class Point{
        int x;
        int y;
        Point(int x,int y){
            this.x = x;
            this.y = y;
        }
    }


    /**
     * 求岛屿数量，就是求连通分量的个数，可以用图的深度优先遍历和广度优先遍历或者并查集
     * @param grid
     * @return
     */
    public int numIslands(char[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        boolean[][] isVisited = new boolean[m][n];

        Deque<Point> queue = new LinkedList<>();

        int result = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(!isVisited[i][j] && grid[i][j] == '1'){
                    isVisited[i][j] = true;
                    result++;
//                    dfs(grid,isVisited,i,j); //深度优先遍历
                    
                    bfs(grid,isVisited,i,j,queue);
                }


            }
        }

        return result;
    }

    /**
     * 广度优先遍历
     * @param grid
     * @param isVisited
     * @param x
     * @param y
     * @param queue
     */
    private void bfs(char[][] grid, boolean[][] isVisited, int x, int y, Deque<Point> queue) {
        isVisited[x][y] = true;
        queue.addLast(new Point(x,y));
        while(!queue.isEmpty()){
            Point curPoint = queue.removeFirst();
            for (int i = 0; i < dir.length; i++) {
                int nextX = curPoint.x + dir[i][0];
                int nextY = curPoint.y + dir[i][1];
                // 判断是否越界
                if(nextX < 0 || nextX >= grid.length || nextY < 0 || nextY>= grid[0].length) continue;

                //将它相邻的未被访问过的岛屿放入队列中
                if(grid[nextX][nextY] == '1' && !isVisited[nextX][nextY]){
                    isVisited[nextX][nextY] = true;
                    queue.addLast(new Point(nextX,nextY));
                }

            }
        }
    }


    /**
     * 深度优先遍历
     * @param grid
     * @param isVisited
     * @param x
     * @param y
     */
    private void dfs(char[][] grid, boolean[][] isVisited, int x, int y) {

//        //递归结束的条件
//        if(grid[x][y] == '0' || isVisited[x][y]) return;
//        isVisited[x][y] = true;

        //1、对于传递进来的坐标x，y分别进行四个方向的深度优先遍历
        for (int i = 0; i < dir.length; i++) {
            //2、获取当前方向上的坐标
            int nextX = x + dir[i][0];
            int nextY = y + dir[i][1];

            //3、判断坐标是否越界，越界则直接下一个点
            if(nextX < 0 || nextX >= grid.length || nextY < 0 || nextY >= grid[0].length) continue;
            //4、没有越界那么进行当前方向上的坐标进行深度优先遍历
            if(grid[nextX][nextY] == '1' && !isVisited[nextX][nextY]){
                isVisited[nextX][nextY] = true;
                dfs(grid,isVisited,nextX,nextY);
            }


        }
    }

    public static void main(String[] args) {
        char[][] grid = {{'1','1','1','1','0'},
                {'1','1','0','1','0'},
                {'1','1','0','0','0'},
                {'0','0','0','0','0'}};
//        Scanner sc = new Scanner(System.in);
//        int N = sc.nextInt();
//        int M = sc.nextInt();
//        int[][] grid = new int[N][M];
//        for (int i = 0; i < N; i++) {
//            for (int j = 0; j < M; j++) {
//                grid[i][j] = sc.nextInt();
//            }
//        }
//        sc.close();
        NumIslands_200 test = new NumIslands_200();
        int result = test.numIslands(grid);
        System.out.println(result);
    }
}
